/**
 * 找出给定数组中的最长递增子序列（LIS）
 * @param {Array} arr - 输入的数组
 * @returns {Array} - 最长递增子序列的索引数组
 */
function getSequence(arr) {
  // 复制一份数组，用于记录每个元素在最长递增子序列中的前一个元素的索引
  const pre = arr.slice();
  // 初始化结果数组，存储最长递增子序列的索引，初始时包含第一个元素的索引
  const result = [0];
  // 声明用于循环和二分查找的临时变量
  let i, j, u, v, c;
  // 获取数组的长度
  const len = arr.length;

  // 调试断点，方便调试代码
  debugger;

  // 遍历数组中的每个元素
  for (i = 0; i < len; i++) {
    // 获取当前元素
    const arrI = arr[i];
    // 跳过值为 0 的元素
    if (arrI !== 0) {
      // 获取结果数组中最后一个元素的索引
      j = result[result.length - 1];
      // 如果当前元素大于结果数组中最后一个元素
      if (arr[j] < arrI) {
        // 记录当前元素的前一个元素的索引
        pre[i] = j;
        // 将当前元素的索引添加到结果数组中
        result.push(i);
        // 跳过本次循环的剩余部分，继续下一次循环
        continue;
      }
      // 二分查找的左边界
      u = 0;
      // 二分查找的右边界
      v = result.length - 1;
      // 二分查找，找到第一个大于等于当前元素的位置
      while (u < v) {
        // 计算中间位置
        c = (u + v) >> 1;
        // 如果中间位置的元素小于当前元素
        if (arr[result[c]] < arrI) {
          // 缩小左边界
          u = c + 1;
        } else {
          // 缩小右边界
          v = c;
        }
      }
      // 如果当前元素小于二分查找找到的位置的元素
      if (arrI < arr[result[u]]) {
        // 如果 u 大于 0，记录当前元素的前一个元素的索引
        if (u > 0) pre[i] = result[u - 1];
        // 更新结果数组中该位置的元素为当前元素的索引
        result[u] = i;
      }
    }
    // 打印当前结果数组，方便调试
    console.log(result);
  }
  // 获取结果数组的长度
  u = result.length;
  // 获取结果数组中最后一个元素的索引
  v = result[u - 1];
  // 回溯重建最长递增子序列
  while (u-- > 0) {
    // 将结果数组中的索引替换为实际的元素索引
    result[u] = v;
    // 更新 v 为 pre[v]，继续回溯
    v = pre[v];
  }
  // 返回最长递增子序列的索引数组
  return result;
}





const ls = getSequence([5, 3, 4, 0, 2, 8, 6, 7, 1]);
/**
[0]
demo.js:32 
[1]
demo.js:32 
(2) [1, 2]
demo.js:32 
(2) [4, 2]
demo.js:32 
(3) [4, 2, 6]
demo.js:32 
(4) [8, 2, 6, 7]
demo.js:56 
(4) [1, 2, 6, 7]0
*/
console.log(ls);


const arr = [1,2,'',4]
const arr2 = arr.filter(Boolean)
console.log(arr2);
